﻿//----------------------------------------------------------------
// Desc: 各种数据对象容器
// Edit: ShowLong, http://blog.csdn.net/showlong
//
// Date Created: 2010-06-11
//
// Update Date : 2010-11-20, showlong
//   增加 FMemoryBlock 类
//
// Update Date : 2010-12-09, showlong
//   增加 FMemoryStack 类
//
// Update Data : 2011-12-23, showlong
//   增加 FMemoryString
//
// Copyright (c) Fuel4D (http://www.fuel4d.com), All rights reserved.
//
//   FMemoryHeap        内存堆（固定大小数组）
//   FMemoryBlock       内存块（动态大小数组）
//   FMemoryChain       对象链（断开的数组，但连续访问）
//   FMemoryPool        对象内存池（断开的数组，但非连续访问）
//   FMemoryStack       复合类型堆栈
//   FMemoryString      字符串内存池
//----------------------------------------------------------------
#pragma once


//----------------------------------------------------------------
// 内存堆（固定大小数组）
//   1. 本类固定长度，分配时从当前分配位置后面连续分配，释放时从使用的尾部释放。
//   2. 在堆生存期内可引用成员地址，请注意分配函数出来的地址是否是空。
//   3. 本类构建与消毁时会调用对象构造与析构，但类本身内部分配与释放函数不调用。
//   4. 本类不适合每次内部分配需要重新构造对象的对象数组。
//   5. 本类没有验证与STL库兼容器与嵌套能力，请谨慎使用。
//
// ._Ty 数据类型
// ._Count 数组大小
//----------------------------------------------------------------
template < typename _Ty, const size_t _Count >
class FMemoryHeap : public IFMemObject
{
    typedef FMemoryHeap< _Ty, _Count > _MyTy;

    FDECLARE_CLASS(FMemoryHeap)

public:
    explicit FMemoryHeap()
        :nAllocateRef(0)
    {}
    virtual~FMemoryHeap()
    { release(); }

    FINLINE size_t size(){ return nAllocateRef; }
    FINLINE size_t capacity(){ return _Count; }
    FINLINE _Ty* allocate(const size_t count = 1);
    FINLINE _Ty* deallocate(const size_t count = 1);
    FINLINE void release(){ clear(); }
    FINLINE void clear(){ nAllocateRef = 0; }
    FINLINE _Ty* address(){ return vData; }
    FINLINE _Ty* push_back(const _Ty& vl){ _Ty* p = allocate(1); if (p) *p = vl; return p; }
    FINLINE _Ty* pop_back(){ return deallocate(1); }
    FINLINE _Ty* begin(){ return vData; }
    FINLINE _Ty* back(){ if (nAllocateRef > 0) return vData + nAllocateRef - 1; return 0; }
    FINLINE bool empty(){ return nAllocateRef == 0; }
    FINLINE bool full(){ return nAllocateRef == _Count; }
    FINLINE bool isvalid(const _Ty* ptr){ return ptr >= vData && ptr < vData + nAllocateRef; }
    FINLINE _Ty& operator[](const size_t idx)
    {
        FASSERT(idx >= 0 && idx < nAllocateRef, _T("访问无效索引"));
        return vData[idx];
    }

protected:
    size_t nAllocateRef;
    _Ty vData[_Count];
};
template < typename _Ty, const size_t _Count >
FINLINE _Ty* FMemoryHeap< _Ty, _Count >::allocate(const size_t count)
{
    FASSERT(count + nAllocateRef <= _Count && count > 0, _T("要求分配的数量太多"));
    if (nAllocateRef + count > _Count || count <= 0)
        return 0;
    nAllocateRef += count;
    return vData + nAllocateRef - count;
}
template < typename _Ty, const size_t _Count >
FINLINE _Ty* FMemoryHeap< _Ty, _Count >::deallocate(const size_t count)
{
    FASSERT(count <= nAllocateRef && count > 0, _T("不法释放这么多数据"));
    if (count > nAllocateRef)
        return 0;
    nAllocateRef -= count;
    return back();
}


//----------------------------------------------------------------
// 内存块（动态大小数组）
//   1. 本固长度不固定，容量不足时自动按固定增量方式扩展，不能引用成员地址。
//   2. 构造本类时可指定预分配数量，或者调用reserve预分配内存。
//   3. 本类构建与消毁时会调用对象构造与析构，但类本身内部分配与释放函数不调用。
//   4. 首次分配不参与增量处理，如果出现不足再以20%增量增加内存容量。
//   5. 本类不适合每次内部分配需要重新构造对象的对象数组。
//   6. 本类没有验证与STL库兼容器与嵌套能力，请谨慎使用。
//
// ._Ty 数据类型
//----------------------------------------------------------------
template < typename _Ty >
class FMemoryBlock : public IFMemObject
{
    typedef FMemoryBlock< _Ty > _MyTy;

    FDECLARE_CLASS(FMemoryBlock)

public:
    explicit FMemoryBlock(const size_t size = 0)
        :nAllocateRef(0)
        ,nCapacity(0)
        ,vData(0)
    {
        if (size > 0)
            resize(size);
    }
    explicit FMemoryBlock(const _MyTy& _ty)
        :nAllocateRef(0)
        ,nCapacity(0)
        ,vData(0)
    {
        operator=(_ty);
    }
    virtual~FMemoryBlock()
    {
        release();
    }

    FINLINE size_t size(){ return nAllocateRef; }
    FINLINE size_t capacity(){ return nCapacity; }
    FINLINE _Ty* allocate(const size_t count);
    FINLINE _Ty* deallocate(const size_t count);
    FINLINE void reserve(const size_t count);
    FINLINE void resize(const size_t count){ nAllocateRef = 0; allocate(count); }
    FINLINE void clear(){ nAllocateRef = 0; }
    FINLINE void release();
    FINLINE _Ty* address(){ return vData; }
    FINLINE _Ty* push_back(const _Ty& vl){ _Ty* p = allocate(1); *p = vl; return p; }
    FINLINE _Ty* pop_back(){ return deallocate(1); }
    FINLINE _Ty* begin(){ return vData; }
    FINLINE _Ty* back(){ if (nAllocateRef > 0) return vData + nAllocateRef - 1; return 0; }
    FINLINE bool empty(){ return nAllocateRef == 0; }
    FINLINE bool full(){ return nAllocateRef == nCapacity; }
    FINLINE bool isvalid(const _Ty* ptr){ return ptr >= vData && ptr < vData + nAllocateRef; }
    FINLINE _Ty& operator[](const size_t idx)
    {
        FASSERT(idx >= 0 && idx < nAllocateRef, _T("访问无效索引"));
        return vData[idx];
    }
    FINLINE void operator=(const _MyTy& r)
    {
        if (nCapacity < r.nCapacity)
        {
            free_memory(vData, nCapacity);
            nCapacity = r.nCapacity;
            vData = alloc_memory(nCapacity);
        }
        nAllocateRef = r.nAllocateRef;
        for (size_t i = 0; i < nAllocateRef; ++i)
            vData[i] = r.vData[i];
    }
    FINLINE size_t idx(const _Ty* ptr)
    {
        return (ptr - vData);
    }

private:
    FINLINE _Ty* alloc_memory(size_t size)
    {
        _Ty* buf = (_Ty*)FAlloc(BYTE, sizeof(_Ty)*size);
        for (size_t i = 0; i < size; ++i)
            FNewPT(buf + i, _Ty);
        return buf;
    }
    FINLINE void free_memory(_Ty*& p, size_t count)
    {
        for (size_t i = 0; i < count; ++i)
            p[i].~_Ty();
        FFree(p);
    }

protected:
    size_t nAllocateRef, nCapacity;
    _Ty* vData;
};
template < typename _Ty >
FINLINE _Ty* FMemoryBlock< _Ty >::allocate(const size_t count)
{
    if (count <= 0)
        return 0;
    if (!vData) // 首次分配
    {
        FASSERT(nAllocateRef == 0, _T("严重错误"));
        nAllocateRef = nCapacity = count;
        vData = alloc_memory(nCapacity);
        return vData;
    }
    if (nAllocateRef + count > nCapacity) // 容量不足，重新分配
    {
        size_t nNewCapacity = nAllocateRef + count;
        nNewCapacity += nNewCapacity/5; // 增加20%
        _Ty* pNew = alloc_memory(nNewCapacity);
        for (size_t i = 0; i < nCapacity; ++i)
            pNew[i] = vData[i];
        free_memory(vData, nCapacity);
        vData = pNew, nCapacity = nNewCapacity;
    }
    nAllocateRef += count;
    return vData + nAllocateRef - count;
}
template < typename _Ty >
FINLINE _Ty* FMemoryBlock< _Ty >::deallocate(const size_t count)
{
    FASSERT(count <= nAllocateRef && count > 0, _T("不法释放这么多数据"));
    if (nAllocateRef < count)
        return 0;
    nAllocateRef -= count;
    return back();
}
template < typename _Ty >
FINLINE void FMemoryBlock< _Ty >::reserve(const size_t count)
{
    if (count <= nCapacity)
        return;
    FAutoVariable<size_t> vl(nAllocateRef, 0);
    allocate(count);
}
template < typename _Ty >
FINLINE void FMemoryBlock< _Ty >::release()
{
    free_memory(vData, nCapacity);
    nAllocateRef = nCapacity = 0;
}


//----------------------------------------------------------------
// 对象链（断开的数组，但连续访问）
//   1. 每个链对象由N个固定大小的堆对象组成，在链生存期内可引用成员地址。
//   2. 由于是断开的，所以只能单个分配和单个释放。
//   3. 对于有下标访问需求，且下标值较的对象本类不适合。
//   4. 本类不适合每次内部分配需要重新构造对象的对象数组。
//   5. 本类没有验证与STL库兼容器与嵌套能力，请谨慎使用。
//
// ._Ty 数据类型
// ._HeapObjCount 链中每个堆的对象数量
//----------------------------------------------------------------
template < typename _Ty, const size_t _HeapObjCount >
class FMemoryChain : public IFMemObject
{
    typedef FMemoryChain< _Ty, _HeapObjCount > _MyTy;
    typedef FMemoryHeap< _Ty, _HeapObjCount > _HeapTy;

    FDECLARE_CLASS(FMemoryChain)

public:
    explicit FMemoryChain()
        :pNext(0)
        ,pPrev(0)
    {}
    virtual~FMemoryChain()
    { release(); }

    FINLINE size_t size() { return nObject.size() + (pNext ? pNext->size() : 0); }
    FINLINE size_t capacity() { return nObject.capacity() + (pNext ? pNext->capacity() : 0); }
    FINLINE _Ty* allocate();
    FINLINE void deallocate();
    FINLINE void clear() { if (pNext) pNext->clear(); nObject.clear(); }
    FINLINE void release() { if (pNext) { pNext->release(); FDel(pNext); } nObject.release(); }
    FINLINE void tidy();
    FINLINE _Ty* push_back(const _Ty& vl){ _Ty* p = allocate(); *p = vl; return p; }
    FINLINE void pop_back(){ deallocate(); }
    FINLINE _Ty* begin(){ if (nObject.empty()) return 0; return nObject.begin(); }
    FINLINE _Ty* back(){ if (pNext && !pNext->empty()) return pNext->back(); if (nObject.empty()) return 0; return nObject.back(); }
    FINLINE bool empty(){ return nObject.empty() && (pNext ? pNext->empty() : true); }
    FINLINE bool full(){ return nObject.full() && (pNext ? pNext->full() : true); }
    FINLINE _Ty& operator[](const size_t idx)
    {
        FASSERT(!pPrev, _T("只能从根部按索引取值"));
        FASSERT(idx >= 0 && idx < size(), _T("访问无效索引"));
        int loop_c = int(idx / _HeapObjCount);
        size_t heap_index = idx - loop_c * _HeapObjCount;
        _MyTy* pDst = this;
        while (loop_c--)
            pDst = pDst->pNext;
        FASSERT(pDst, _T("严重错误"));
        return pDst->nObject[heap_index];
    }

private:
    FINLINE void operator = (const _MyTy&){ FASSERT_STR(_T("本容器不是为动态变化对象设计的内存链")); }
	FMemoryChain(_MyTy& _ty){ operator=(_ty); }

protected:
    _MyTy* pNext, * pPrev;
    _HeapTy nObject;
};
template < typename _Ty, const size_t _HeapObjCount >
FINLINE _Ty* FMemoryChain< _Ty, _HeapObjCount >::allocate()
{
    if (!nObject.full())
        return nObject.allocate(1);
    if (!pNext)
    {
        pNext = FNew(_MyTy);
        pNext->pPrev = this;
    }
    return pNext->allocate();
}
template < typename _Ty, const size_t _HeapObjCount >
FINLINE void FMemoryChain< _Ty, _HeapObjCount >::deallocate()
{
    if (pNext && !pNext->nObject.empty())
        pNext->deallocate();
    else
        nObject.deallocate(1);
}
template < typename _Ty, const size_t _HeapObjCount >
FINLINE void FMemoryChain< _Ty, _HeapObjCount >::tidy()
{
    if (!pNext)
        return;
    pNext->tidy();
    if (pNext->nObject.empty())
        FDel(pNext);
}


//----------------------------------------------------------------
// 对象内存池
//   1. 由N条固定大小的堆组成，非连续分配，在链生存期内可引用成员地址。
//   2. 由于是断开的，所以只能单个分配和单个释放。
//   3. 本类在分配与释放的时候自动构造与析构对象（可选）。
//   4. 本类没有验证与STL库兼容器与嵌套能力，请谨慎使用。
//
// ._Ty 数据类型
// ._HeapObjCount 链中每个堆的对象数量
// ._TLK 链表头的锁类型，默认空锁
//----------------------------------------------------------------
template < typename _Ty, const WORD _HeapObjCount, typename _TLK = FLock_Nil >
class FMemoryPool : public IFMemObject
{
    typedef FMemoryPool < _Ty, _HeapObjCount, _TLK > _MyTy_Org;
    typedef FMemoryPool < _Ty, _HeapObjCount, FLock_Nil > _MyTy;

    enum MEMORY_STATE
    {
        ms_unused = 0xcd,
        ms_using  = 0xcc,
    };

    struct _DataType
    {
        BYTE nData[sizeof(_Ty)];// 必成员必须放在结构首位
        BYTE nUsed;             // 使用状态
        WORD nIdx;              // 在堆中的索引
        _Ty* addr;              // 供直接使用和查看
        FMemoryNode mi;         // 内存所属信息
        _DataType()
            :nUsed(ms_unused)
            ,nIdx(0xFFFF)
        { addr = (_Ty*)nData; mi.size = sizeof(_Ty); }
        FINLINE bool IsUsing(){ return nUsed == ms_using; }
        FINLINE bool IsAvailable(){ return nUsed == ms_unused; }
        FINLINE _Ty* New(FNEW_FUNC)
        { 
            mi.file = file, mi.line = line, mi.func = func, mi.name = name;
            nUsed = ms_using; return addr;
        }
        FINLINE void Del(bool __del){ nUsed = ms_unused; if (__del) addr->~_Ty(); }
    };

    FDECLARE_CLASS(FMemoryPool)

public:
    explicit FMemoryPool()
        :pNext(0)
        ,nNewRef(0)
        ,nNewStart(0)
    {
        for (WORD i = 0; i < _HeapObjCount; ++i)
            nObject[i].nIdx = i;
    }
    virtual~FMemoryPool()
    { release(); }

    FINLINE size_t size() { return nNewRef + (pNext ? pNext->size() : 0); }
    FINLINE size_t capacity() { return _HeapObjCount + (pNext ? pNext->capacity() : 0); }
    FINLINE _Ty* allocate(FNEW_FUNC_API); // 自动参数'FNEW_INFO'
    FINLINE bool deallocate(_Ty*& pData, bool _call_del = false);
    FINLINE void clear(bool _call_del = false);
    FINLINE void release(bool _call_del = false);
    FINLINE void tidy();
    FINLINE bool empty(){ return (nNewRef == 0) && (pNext ? pNext->empty() : true); }
    FINLINE bool full(){ return (nNewRef == _HeapObjCount) && (pNext ? pNext->full() : true); }
    FINLINE bool IsTail(){ return pNext == 0; }
    FINLINE size_t obj_size(){ return sizeof(_DataType); }

private:
    FINLINE void operator = (const _MyTy&){ FASSERT_STR(_T("本容器不是为动态变化对象设计的内存链")); }
	FMemoryPool(const _MyTy& _ty){ operator=(_ty); }

protected:
    _DataType nObject[_HeapObjCount];
    size_t nNewRef, nNewStart;
    _MyTy* pNext;
    _TLK nLock;
};
template < typename _Ty, const WORD _HeapObjCount, typename _TLK >
FINLINE _Ty* FMemoryPool< _Ty, _HeapObjCount, _TLK >::allocate(FNEW_FUNC_API)
{
    FLock_Auto __lk(&nLock);
    if (nNewRef >= _HeapObjCount)
    {
        if (!pNext)
        {
            pNext = (_MyTy*)FAlloc(BYTE, sizeof(_MyTy));
            FNewPT(pNext, _MyTy);
        }
        return pNext->allocate(FNEW_PASS_API);
    }
    for (size_t i = nNewStart; i < _HeapObjCount; ++i)
    {
        if (nObject[i].IsAvailable())
        {
            nNewRef++;
            nNewStart = i + 1;
            return nObject[i].New(FNEW_PASS_API, _Ty::_StaticClassName());
        }
    }
    FASSERT_STR(_T("严重的错误"));
    return 0;
}
template < typename _Ty, const WORD _HeapObjCount, typename _TLK >
FINLINE bool FMemoryPool< _Ty, _HeapObjCount, _TLK >::deallocate(_Ty*& pData, bool _call_del)
{
    if (!pData)
        return false;
    FLock_Auto __lk(&nLock);
    _DataType* pst = (_DataType*)pData;
    if (nNewRef > 0 && pst >= nObject && pst < nObject + _HeapObjCount)
    {
        FASSERT(pst->nIdx >= 0 && pst->nIdx < _HeapObjCount, _T("严重错误"));
        if (nObject[pst->nIdx].IsUsing() && (_Ty*)nObject[pst->nIdx].nData == pData)
        {
            nNewRef--;
            if (nNewStart > pst->nIdx)
                nNewStart = pst->nIdx;
            nObject[pst->nIdx].Del(_call_del);
            pData = 0;
            return true;
        }
        return false;
     }
    if (pNext)
        return pNext->deallocate(pData, _call_del);
    else
        FASSERT_STR(_T("严重的错误"));
    return false;
}
template < typename _Ty, const WORD _HeapObjCount, typename _TLK >
FINLINE void FMemoryPool< _Ty, _HeapObjCount, _TLK >::clear(bool _call_del)
{
    FLock_Auto __lk(&nLock);
    if (pNext)
        pNext->clear(_call_del);
    if (nNewRef > 0)
    {
        for (_DataType* ptr = nObject; ptr < nObject + _HeapObjCount; ++ptr)
        {
            if (ptr->IsUsing())
                ptr->Del(_call_del);
        }
    }
    nNewRef = nNewStart = 0;
}
template < typename _Ty, const WORD _HeapObjCount, typename _TLK >
FINLINE void FMemoryPool< _Ty, _HeapObjCount, _TLK >::release(bool _call_del)
{
    if (pNext)
    {
        pNext->release(_call_del);
        FFree(pNext);
    }
    clear(_call_del);
}
template < typename _Ty, const WORD _HeapObjCount, typename _TLK >
FINLINE void FMemoryPool< _Ty, _HeapObjCount, _TLK >::tidy()
{
    if (!pNext)
        return;
    FLock_Auto __lk(&nLock);
    pNext->tidy();
    if (pNext->nNewRef == 0)
    {
        _MyTy* p = pNext;
        pNext = pNext->pNext;
        p->pNext = 0;
        FFree(p);
    }
}


//----------------------------------------------------------------
// 复合类型堆栈
//   1. 需自已保证出入栈数据类型匹配。
//   2. 由是栈，不考虑构造与析构问题，请自己注意。
//----------------------------------------------------------------
class FMemoryStack : public IFMemObject
{
    typedef FMemoryStack _MyTy;

    FDECLARE_CLASS(FMemoryStack)

public:
    explicit FMemoryStack(size_t size = 0)
    { if (size > 0){ vData.reserve(size); vType.reserve(size); } }
    virtual~FMemoryStack()
    { release(); }

    void release()
    {
        vData.release();
        vType.release();
    }
    template < typename _Ty >
    FINLINE void push_back(const _Ty& vl)
    {
        ItemType _ty;
        _ty.nSize = sizeof(vl);
        FASSERT(_ty.nSize > 0, _T("严重错误"));
        BYTE* pdata = vData.allocate(_ty.nSize);
        FMemcpy(pdata, &vl, _ty.nSize);
        vType.push_back(_ty);
    }
    template < typename _Ty >
    FINLINE bool pop_back(_Ty& _out)
    {
        ItemType* _ty = vType.back();
        if (!_ty)
            return false;
        if (_ty->nSize != sizeof(_Ty))
        {
            FASSERT_STR(_T("数据类型不匹配"));
            return false;
        }
        FMemcpy(&_out, vData.back() - _ty->nSize, _ty->nSize);
        vType.pop_back();
        vData.deallocate(_ty->nSize);
        return true;
    }

private:
    FINLINE void operator = (const _MyTy&){ FASSERT_STR(_T("本容器不是为动态变化对象设计的内存链")); }
	FMemoryStack(const _MyTy& _ty){ operator=(_ty); }

protected:
    struct ItemType{ size_t nSize; };

    FMemoryBlock< BYTE > vData;
    FMemoryBlock< ItemType > vType;
};


//----------------------------------------------------------------
// 字符串内存池
//   1. 由N堆组成，连续分配
//   2. 必须保证最小字符数量满足你的最大字符串数量
// 
// ._CharCount 每个堆的字符数量
// ._Ty 字符集类型
//----------------------------------------------------------------
template < const size_t _CharCount, typename _Ty = NCHAR >
class FMemoryString : public IFMemObject
{
    typedef FMemoryString< _CharCount, _Ty > _MyTy;
    typedef FMemoryHeap< _Ty, _CharCount > _HeapTy;

    FDECLARE_CLASS(FMemoryString)

public:
    explicit FMemoryString()
        :pNext(0)
        ,pPrev(0)
    {}
    virtual~FMemoryString()
    { release(); }

    FINLINE size_t size() { return nObject.size() + (pNext ? pNext->size() : 0); }
    FINLINE size_t capacity() { return nObject.capacity() + (pNext ? pNext->capacity() : 0); }
    FINLINE _Ty* allocate(size_t count);
    FINLINE _Ty* push_back(const _Ty* pstr);
    FINLINE void clear() { if (pNext) pNext->clear(); nObject.clear(); }
    FINLINE void release() { if (pNext) { pNext->release(); FDel(pNext); } nObject.release(); }

private:
    FINLINE void operator=(const _MyTy&){ FASSERT_STR(_T("本容器不是为动态变化对象设计的内存链")); }
	FMemoryString(const _MyTy& _ty){ operator=(_ty); }

protected:
    _MyTy* pNext, * pPrev;
    _HeapTy nObject;
};
template < const size_t _CharCount, typename _Ty >
FINLINE _Ty* FMemoryString< _CharCount, _Ty >::allocate(size_t count)
{
    if (nObject.capacity() < count || count <= 0)
    {
        FASSERT_STR(_T("无法满足分配请求"));
        return 0;
    }
    if (nObject.size() + count > nObject.capacity())
    {
        if (!pNext)
        {
            pNext = FNew(_MyTy);
            pNext->pPrev = this;
        }
        return pNext->allocate(count);
    }
    return nObject.allocate(count);
}
template < const size_t _CharCount, typename _Ty >
FINLINE _Ty* FMemoryString< _CharCount, _Ty >::push_back(const _Ty* pstr)
{
    if (!pstr || !*pstr)
        return 0;
    size_t siz = 0;
    const _Ty* src = pstr;
    while(*src)
        src++, siz++;
    _Ty* p = allocate(siz + 1);
    if (!p)
        return 0;
    FMemcpy(p, pstr, siz * sizeof(_Ty));
    p[siz] = 0;
    return p;
}